#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
#include <time.h>

void Test01()
{
	Heap hp = { 0 };
	HeapInit(&hp);

	int a[] = { 1,2,3,4,5,6};

	int i = 0;
	while (i < sizeof(a)/sizeof(a[0]))
	{
		HeapPush(&hp, a[i]);
		i++;
	}

	HeapPush(&hp, 0);


	HeapPop(&hp);

	int size = GetHeapSize(&hp);
	printf("%d ", size);

	if (!HeapEmpty(&hp))
	{
		printf("false");
	}

	HeapDestroy(&hp);
}

//堆排序
void HeapSort1(int* a,int n)
{
	//借助原数组建堆
	//升序，建大堆
	//降序，建小堆
	int i = 0;
	for (i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}

	//堆顶数据就是最小数据
	int end = n - 1;//n是元素个数，n-1刚好是最后一片叶子的下标
	while (end > 0)
	{
		//将堆顶数据和最后一片叶子交换
		Swap(&a[0], &a[end]);

		AdjustDown(a, 0, end);//此时下标end已经不算在这一次调整的堆里面了。

		end--;
	}
}
//堆排序
//n是数组中元素个数
void HeapSort(int* a, int n)
{
	//升序，建大堆
	//降序，建小堆

	//要求升序、建堆采用向下调整
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)//n是元素个数，n-1表示最后一个叶子的下标，(n-1-1)/2，表示该叶子的父亲。
	{
		AdjustDown(a, i, n);
	}

	//堆排序
	//n代表个数，n-1表示最后一个叶子的下标
	int last = n - 1;//最后一个叶子的下标
	while (last > 0)
	{
		//先交换堆顶数据和最后一个叶子
		Swap(&a[0], &a[last]);

		//对没有删除的数据进行向下调整
		AdjustDown(a, 0, last);

		//删除最后一个数
		last--;
	}

}

void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand((unsigned int)time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

void PrintTopK(int k)
{
	//打开文件
	FILE* pf = fopen("data.txt", "r");
	if (pf == NULL)
	{
		perror("fopen");
		return;
	}

	//先将文件的前10个建成一个小堆
	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc");
		return;
	}

	//取出十个数，存放到kminheap
	int i = 0;
	for (i = 0; i < k; i++)
	{
		fscanf(pf, "%d", &kminheap[i]);
	}

	//将这十个数建成小堆
	for (i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, i, k);
	}

	//从文件中取数据，与栈顶元素比较
	//大于栈顶元素就替换，然后向下调整，反之直接取下一个
	int x = 0;
	while (fscanf(pf, "%d", &x) != EOF)
	{
		if (kminheap[0] < x)
		{
			//替换
			Swap(&kminheap[0], &x);

			//向下调整，使之仍然为小堆
			AdjustDown(kminheap, 0, k);
		}
	}

	//输入最大的前十个数
	printf("最大的前%d个数为：", k);
	for (i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");

	//释放空间
	free(kminheap);
	kminheap = NULL;

	//关闭文件
	fclose(pf);
	pf = NULL;
}

int main()
{
	//Test01();
	//int a[] = { 1,9,7,6,8,3,4,33 };
	//int size = sizeof(a) / sizeof(a[0]);


	//HeapSort(a,size);

	//CreateNDate();

	printf("请输入k->: ");
	int k = 0;
	scanf("%d", &k);

	PrintTopK(k);

	return 0;
}